import java.util.Random;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-07 19:19
 **/

public class QuickSort2Ways {

    private QuickSort2Ways(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr, 0, arr.length - 1);
    }
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
        if (l >= r){
            return;
        }else {
            //arr[l.....p - 1] < v;  arr[p + 1.....r] > v
            int p = partition(arr, l, r);
            sort(arr, l, p - 1);
            sort(arr, p + 1, r);
        }
    }
    // 将整个数组划分为两部分，大于arr[j] 放在arr[j] 后面，小于的放到前面
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r){
        int p = l + (new Random().nextInt(r - l + 1));
        swap(arr, l, p);

        // arr[l+1.....i-1] <= V ;  arr[j+1.....r] >= V
        int i = l + 1, j = r;
        while (true){
            while (i <= j && arr[i].compareTo(arr[l]) < 0){
                i ++;
            }
            while (j >= i && arr[j].compareTo(arr[l]) > 0){
                j --;
            }
            if (i >= j){
                break;
            }
            swap(arr, i, j);
            i ++; j --;
        }
        swap(arr, l, j);
        return j;
    }
    private static <E> void swap(E[] arr, int i, int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
